// 只有最后一层 没有填满
// 所有的节点都大于等于（最大堆） 或 小于等于（最小堆） 它的子节点
// 左侧子节点的位置是 2*index+1
// 右侧子节点的位置是 2*index+2
// 父节点的位置是 (index-1) / 2

// 第K个 最大元素 

// 最小堆类
class MinHeap{
  constructor() {
    this.heap = []
  }
  insert(value) {
    this.heap.push(value)
    this.shiftUp(this.heap.length - 1)
  }
  swap(i1, i2) {
    const temp = this.heap[i1]
    this.heap[i1] = this.heap[i2]
    this.heap[i2] = temp
  }
  getParentIndex(i) {
    return (i-1) >> 1;
  }
  // 上移 移到合适的位置
  shiftUp(index) {
    if(index == 0) return;
    const parentIndex = this.getParentIndex(index)
    if(this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index)
      // 继续上移
      this.shiftUp(parentIndex)
    }
  }
  // 删除堆顶
  // 删除第一个为最后一个  然后往下移
  pop() {
    if(this.size() === 1) return this.heap.shift();
    const top = this.heap[0]
    this.heap[0] = this.heap.pop()
    this.shiftDown(0)
    return top;
  }
  // 获取左节点 
  getLeftIndex(i) {
    return i * 2 + 1
  }
  // 获取右侧节点
  getRightIndex(i) {
    return i * 2 + 2
  }
  // 下移
  shiftDown(index) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    if(this.heap[leftIndex] < this.heap[index]) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex)
    }
    if(this.heap[rightIndex] < this.heap[index]) {
      this.swap(rightIndex, index)
      this.shiftDown(rightIndex)
    }
  }
  // 获取
  peek() {
    return this.heap[0]
  }
  size() {
    return this.heap.length
  }
}
var findKthLargest = function(nums, k) {
  const h = new MinHeap()
  nums.forEach(n=>{
      h.insert(n)
      if(h.size() > k) {
          h.pop()
      }
  })
  return h.peek()
};
findKthLargest([3,2,1,5,6,4], 2)
